﻿#pragma once

//头文件
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>




#define MaxInt 32767		//表示权值的极大值
#define MVNum 100			//最大顶点数

typedef char VerTexType;	//假设定点的数据类型为字符型
typedef int ArcType;		//假设边的权值为整型

//图类型
typedef struct
{
	VerTexType vexs[MVNum];			//顶点表
	ArcType arcs[MVNum][MVNum];		//邻接矩阵
	int vexnum;						//图的当前点数
	int arcnum;						//图的当前边数
}AMGraph;

//辅助数组，记录从U到V-U具有最小权值的边
struct Auxiliary
{
	VerTexType adjvex;	//最小边在U中的顶点
	ArcType lowcost;	//最小边的权值
}closedge[MVNum];

//使用邻接矩阵创建无线网
void CreateUDN(AMGraph* G);

//根据顶点的值，确定顶点在数组中的位置
int LocateVex(AMGraph* G, VerTexType v);

//打印邻接矩阵
void PrintArcs(AMGraph* G);

//Prim算法
//	1.首先，将初始顶点u加入U中，对其余的每一个顶点vj，将closedge[j]均初始化到u的边信息
//	2.循环n-1次，做如下处理
//		a.从各组边closedge中选出最小边closedge[k]，输出此边
//		b.将k加入U中
//		c.更新剩余的每组最小边信息closedge[j]，对于V-U中的边，
//		  新增加了一条从k到j的边，如果新边的权值比closedge[j].lowcost小，
//		  则将closedge[j].lowcost更新为新边的权值

//无向网G以邻接矩阵形式存储，从顶点u出发构造G的最小生成树T，输出T的各条边
void MiniSpanTree_Prim(AMGraph* G, VerTexType u);

//查找closedge数组中的最小权值
int Min(AMGraph* G, struct Auxiliary* closedge);







